#include "DoublyLinkedList.h"

// 创建返回链表的头结点.
ListNode* ListCreate() {
    ListNode* head = MALLOC(ListNode, 1);
    head->_next = head;
    head->_prev = head;
    return head;
}

ListNode* NodeCreate(DataType data) {
    ListNode* newNode = MALLOC(ListNode, 1);
    newNode->_next = newNode->_prev = NULL;
    return newNode;
}

ListNode* NodeWithPointerCreate(ListNode* prev, DataType data, ListNode* next) {
    ListNode* newNode = MALLOC(ListNode, 1);
    newNode->_prev = prev;
    newNode->_next = next;
    newNode->_data = data;
    return newNode;
}
// 双向链表销毁
void ListDestroy(ListNode* pHead) {
    assert(pHead);
    if (!IsEmpty(pHead)) {
        ListNode* cur = pHead->_next;
        while (cur != pHead) {
            ListNode* temp = cur;
            cur = cur->_next;
            free(temp);
        }
    }

    free(pHead);
}
// 双向链表打印
void ListPrint(ListNode* pHead) {
    assert(pHead);
    if (IsEmpty(pHead)) {
        printf("[]\n");
        return;
    }
    printf("[HEAD <> ");
    for (ListNode* cur = pHead->_next; cur != pHead; cur = cur->_next) {
        printf("%d <> ", cur->_data);
    }
    printf("TAIL]\n");
}
// 双向链表尾插
void ListPushBack(ListNode* pHead, DataType data) {
    // ListNode 放进去的原因是IsEmpty内包含pHead的空值判断
    if (IsEmpty(pHead)) {
    ListNode* newNode = NodeWithPointerCreate(pHead, data, pHead);
        pHead->_next = newNode;
        pHead->_prev = newNode;
    } else {
    ListNode* newNode = NodeWithPointerCreate(pHead->_prev, data, pHead);
        pHead->_prev = newNode;
        newNode->_prev->_next = newNode;
    }

}
// 双向链表尾删
void ListPopBack(ListNode* pHead) {
    if (IsEmpty(pHead)) {
        printf("ListPopBack: Empty List.\n");
        return;
    }
    ListNode* temp = pHead->_prev;
    temp->_prev->_next = pHead;
    pHead->_prev = temp->_prev;
    free(temp);
}
// 双向链表头插
void ListPushFront(ListNode* pHead, DataType data) {
    if (IsEmpty(pHead)) {
        ListNode* newNode = NodeWithPointerCreate(pHead, data, pHead);
        pHead->_next = newNode;
        pHead->_prev = newNode;
    } else {
        ListNode* newNode = NodeWithPointerCreate(pHead, data, pHead->_next);
        pHead->_next = newNode;
        newNode->_next->_prev = newNode;
    }
}
// 双向链表头删
void ListPopFront(ListNode* pHead) {
    if (IsEmpty(pHead)) {
        printf("ListPopFront: Empty List.\n");
        return;
    }
    ListNode* temp = pHead->_next;
    temp->_next->_prev = pHead;
    pHead->_next = temp->_next;
    free(temp);
}
// 双向链表查找
ListNode* ListFind(ListNode* pHead, DataType data) {
    if (!IsEmpty(pHead)) {
        for (ListNode* cur = pHead->_next; cur != pHead; cur = cur->_next) {
            if (cur->_data == data) {
                return cur;
            }
        }
    }
    printf("Not Found %d.\n", data);
    return NULL;
}
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, DataType data) {
    assert(pos);
    ListNode* newNode = NodeWithPointerCreate(pos->_prev, data, pos);
    pos->_prev = newNode;
    newNode->_prev->_next = newNode;
}
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos) {
    assert(pos);
    ListNode* temp = pos;
    pos->_prev->_next = pos->_next;
    pos->_next->_prev = pos->_prev;
    free(temp);
}

bool IsEmpty(ListNode* pHead) {
    assert(pHead);
    return pHead->_next == pHead;
}